# -*- coding: utf-8 -*-
import random
import sys
from queue import Queue, PriorityQueue
from queue import LifoQueue  # LifoQueue是栈

from PyQt5.QtCore import Qt, QRectF, QTimer
from PyQt5.QtWidgets import QApplication, QMainWindow, QGraphicsItem
from ui import *

WIDTH, HEIGHT = 800, 800  # Graphicsview的尺寸
COL_LEN, ROW_LEN = 50, 50  # 格子的长度
COL_NUM, ROW_NUM = 20, 20  # 格子的数量
FIND, GENERATE = 0, 0  # 生成方式，走迷宫方式
maz = -np.ones((ROW_NUM, COL_NUM))  # 迷宫矩阵
st = ()
dx, dy = ROW_NUM - 2, COL_NUM - 1  # 终点
record, ans, process = [], [], []  # 记录答案


class DFSg(object):
    def __init__(self, width=11, height=11):

        # 确保迷宫的长和宽均为奇数
        self.width = (width // 2) * 2 + 1
        self.height = (height // 2) * 2 + 1
        self.start = [1, 0]
        self.destination = [self.height - 2, self.width - 1]
        self.matrix = None

    def generate_matrix_dfs(self):
        # 地图初始化，并将出口和入口处的值设置为0
        self.matrix = -np.ones((self.height, self.width))
        self.matrix[self.start[0], self.start[1]] = 0
        self.matrix[self.destination[0], self.destination[1]] = 0
        # 列表生成式
        visit_flag = [[0 for i in range(self.width)]
                      for j in range(self.height)]

        def check(row, col, row_, col_):
            temp_sum = 0
            for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                temp_sum += self.matrix[row_ + d[0]][col_ + d[1]]
            return temp_sum <= -3

        def dfs(row, col):
            visit_flag[row][col] = 1
            self.matrix[row][col] = 0
            if row == self.start[0] and col == self.start[1] + 1:
                return

            directions = [[0, 2], [0, -2], [2, 0], [-2, 0]]
            random.shuffle(directions)
            for d in directions:
                row_, col_ = row + d[0], col + d[1]
                if row_ > 0 and row_ < self.height - 1 and col_ > 0 and col_ < self.width - 1 and visit_flag[row_][
                    col_] == 0 and check(row, col, row_, col_):
                    if row == row_:
                        visit_flag[row][min(col, col_) + 1] = 1
                        self.matrix[row][min(col, col_) + 1] = 0
                    else:
                        visit_flag[min(row, row_) + 1][col] = 1
                        self.matrix[min(row, row_) + 1][col] = 0
                    dfs(row_, col_)

        dfs(self.destination[0], self.destination[1] - 1)
        self.matrix[self.start[0], self.start[1] + 1] = 0


class PRIMg(object):
    def __init__(self, width=11, height=11):

        self.width = (width // 2) * 2 + 1
        self.height = (height // 2) * 2 + 1
        self.start = [1, 0]
        self.destination = [self.height - 2, self.width - 1]
        self.matrix = None

    # prim与广度优先类似
    def generate_matrix_prim(self):
        # 地图初始化，并将出口和入口处的值设置为0
        self.matrix = -np.ones((self.height, self.width))

        def check(row, col):
            temp_sum = 0
            for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                temp_sum += self.matrix[row + d[0]][col + d[1]]
            return temp_sum < -3

        list = []
        row, col = (np.random.randint(1, self.height - 1) // 2) * 2 + 1, (
                np.random.randint(1, self.width - 1) // 2) * 2 + 1
        list.append((row, col, -1, -1))
        while len(list) != 0:
            row, col, r_, c_ = list.pop(np.random.randint(0, len(list)))
            if check(row, col):
                self.matrix[row, col] = 0
                if r_ != -1 and row == r_:
                    self.matrix[row][min(col, c_) + 1] = 0
                elif r_ != -1 and col == c_:
                    self.matrix[min(row, r_) + 1][col] = 0
                for d in [[0, 2], [0, -2], [2, 0], [-2, 0]]:
                    row_, col_ = row + d[0], col + d[1]
                    if row_ > 0 and row_ < self.height - 1 and col_ > 0 and col_ < self.width - 1 and self.matrix[row_][
                        col_] == -1:
                        list.append((row_, col_, row, col))

        self.matrix[self.start[0], self.start[1]] = 0
        self.matrix[self.destination[0], self.destination[1]] = 0


class Board(QMainWindow, Ui_MainWindow):
    def __init__(self):
        super(Board, self).__init__()
        self.setupUi(self)
        self.graphicsView.scene = QtWidgets.QGraphicsScene(0, 0, WIDTH, HEIGHT)
        maze = Maze()
        maze.setPos(0, 0)
        self.graphicsView.scene.addItem(maze)
        self.graphicsView.setScene(self.graphicsView.scene)
        self.connecter()

        self.show()

    def connecter(self):
        self.pushButton.clicked.connect(self.draw)
        self.pushButton_2.clicked.connect(self.start)
        self.pushButton_3.clicked.connect(self.randsd)

    def randsd(self):
        global dx, dy, maz, COL_NUM, ROW_NUM, Maze, st
        # print(maz)

        while True:
            dx = random.randint(1, COL_NUM - 1)
            dy = random.randint(1, ROW_NUM - 1)
            if maz[dx][dy] == 0:
                break
        while True:
            st[0] = random.randint(1, COL_NUM - 1)
            st[1] = random.randint(1, ROW_NUM - 1)
            if maz[st[0]][st[1]] == 0:
                break
        self.pushButton_2.setEnabled(True)

    def start(self):

        global FIND, ROUTE, ans, record
        ans = []
        record = []
        FIND = int(self.comboBox_2.currentIndex())
        self.search()
        maze = Maze()
        maze.setPos(0, 0)
        self.pushButton_2.setEnabled(False)
        self.update(maze)

    def draw(self):
        global WIDTH, record
        global COL_NUM, ROW_NUM, COL_LEN, ROW_LEN, GENERATE, maz, ans
        ans = []
        record = []
        COL_NUM = int(self.lineEdit_2.text())
        ROW_NUM = int(self.lineEdit.text())
        if COL_NUM >= 5 and ROW_NUM >= 5:
            GENERATE = int(self.comboBox.currentIndex())
            self.updateParameter()
            maze = Maze()
            maze.setPos(0, 0)
            self.update(maze)
            self.pushButton_2.setEnabled(True)
            self.pushButton_3.setEnabled(True)
        else:
            print("长宽必须大于等于五")

    def generate(self):
        global maz
        gen = Gen()
        maz = np.ones((ROW_NUM + 2, COL_NUM + 2))
        if (GENERATE == 0):
            gen.dfsg()
        if (GENERATE == 1):
            gen.primg()

    def updateParameter(self):
        global WIDTH, dx, dy
        global COL_NUM, ROW_NUM, COL_LEN, ROW_LEN
        self.generate()
        ROW_NUM, COL_NUM = maz.shape
        COL_LEN = int(WIDTH / COL_NUM)
        ROW_LEN = int(HEIGHT / ROW_NUM)
        dx = ROW_NUM - 2
        dy = COL_NUM - 1

    def search(self):
        global FIND, record, ans, st
        if (FIND == 0):
            record.append((st[0], st[1]))
            dfs(st[0], st[1])
            ans = list(ans)

        if (FIND == 1):
            bfs((st[0], st[1]))
            ans = list(ans)

    def update(self, maze):
        self.graphicsView.scene.addItem(maze)
        self.graphicsView.setScene(self.graphicsView.scene)
        self.graphicsView.setBackgroundBrush(Qt.white)
        self.show()


class Gen():
    def dfsg(self):
        global maz, st
        k = DFSg(ROW_NUM, COL_NUM)
        k.generate_matrix_dfs()
        maz = k.matrix
        st = k.start

    def primg(self):
        global maz, st
        k = PRIMg(ROW_NUM, COL_NUM)
        k.generate_matrix_prim()
        maz = k.matrix
        st = k.start


def Keep(temp):
    global ans, record
    ans = tuple(temp)


def dfs(x, y):
    # 递归式
    global dx, dy, record, w
    if x == dx and y == dy:
        Keep(record)
        return
    for (kx, ky) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        if (check(kx + x, ky + y)):
            record.append((kx + x, ky + y))
            dfs(kx + x, ky + y)
            record.pop()


def bfs(t):
    # 利用辅助队列
    global que, dx, dy, record, st
    lis = {}
    visited = [(st[0], st[1])]
    que = Queue()
    que.put(t)
    while que:
        temp = que.get()
        if temp[0] == dx and temp[1] == dy:
            break
        for (kx, ky) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            x = kx + temp[0]
            y = ky + temp[1]
            if (x > 0 and y > 0 and x < ROW_NUM and y < COL_NUM and maz[x][y] == 0 and (x, y) not in visited):
                que.put((x, y))
                visited.append((x, y))
                lis[(x, y)] = (temp[0], temp[1])
                if (x == dx and y == dy):
                    break
    record.append((dx, dy))
    (x, y) = lis[(dx, dy)]
    record.append((x, y))
    while (x, y) != (st[0], st[1]):
        (x, y) = lis[x, y]
        record.append((x, y))
    Keep(record)


def check(x, y):
    global maz, record, ROW_NUM, COL_NUM
    if (x >= 0 and y >= 0 and x < ROW_NUM and y < COL_NUM and maz[x][y] == 0 and (x, y) not in record):
        return True
    return False


class Maze(QGraphicsItem):
    def __init__(self):
        super(Maze, self).__init__()

    def boundingRect(self):
        return QRectF(0, 0, 800, 800)

    def paint(self, painter, option, widget):
        global COL_INTERVAL, ROW_INTERVAL
        global WIDTH, COL_NUM, ROW_NUM
        global COL_LEN, ROW_LEN, maz, ROUTE
        for i in range(COL_NUM):
            for j in range(ROW_NUM):
                if (maz[i][j] != 0):
                    painter.setPen(Qt.black)
                    painter.setBrush(Qt.black)
                    painter.drawRect(i * (COL_LEN),
                                     j * (ROW_LEN), COL_LEN, ROW_LEN)
                if ((i, j) in ans[1:-1]):
                    painter.setPen(Qt.magenta)
                    b = QtGui.QBrush(Qt.SolidPattern)
                    b.setColor(Qt.magenta)
                    painter.setBrush(b)
                    painter.drawRect(i * (COL_LEN),
                                     j * (ROW_LEN), COL_LEN, ROW_LEN)

                if ((i, j) in ans[-1:]):
                    painter.setPen(Qt.yellow)
                    painter.setBrush(Qt.red)
                    painter.drawRect(i * (COL_LEN),
                                     j * (ROW_LEN), COL_LEN, ROW_LEN)
                if (i, j) in ans[:1]:
                    painter.setPen(Qt.yellow)
                    painter.setBrush(Qt.green)
                    painter.drawRect(i * (COL_LEN),
                                     j * (ROW_LEN), COL_LEN, ROW_LEN)


def main():
    app = QApplication(sys.argv)
    w = Board()
    w.show()
    sys.exit(app.exec_())


main()
